package com.order.www;

/**
 * Creared with IntelliJ IDEA.
 * Description:背包问题
 * User:yxd
 * Date:2022-03-23
 * Time:22:39
 */
import java.util.Scanner;
public class Dp11 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();;//N个物品
        int M = input.nextInt();//M大的空间
        int[] W = new int[N];//每个物品所占的空间
        int[] A = new int[N];//每个物品的价值
        for (int i = 0; i < N; i++) {
            W[i] = input.nextInt();
            A[i] = input.nextInt();
        }
        System.out.println(maxValue(W, A, M));
    }
    public static int maxValue(int[] W,int[] V,int m){//m大的容量
        int len1 = W.length;

        int[][] dp = new int[len1 + 1][m+ 1];
        //状态定义:F(i,j)j大的空间内能放前i个物品的最大价值
        //状态转移方程:*i-1个物品能放入(也就是第i个物品) 放第i个进去的价值:dp[i][j - W[i - 1]] + V[i -1]);
        //不放:dp[i-1,j]
        //放不进去这个物品那就直接是dp[i-1,j]
        //初始值不放物品时价值为0 没有物品时价值为0
        for(int i = 0;i <= len1;i ++){
            dp[i][0] = 0;
        }
        for(int i = 0;i <= m;i ++){
            dp[0][i] = 0;
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= m; j++) {
                if(j >= W[i - 1]){
                    dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - W[i - 1]] + V[i -1]);
                }else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[len1][m];
    }
}
